package Sort;

public class sort8 {
    //计数排序
    public static void main(String[] args) {
        int[] arr = {10, 5, 9, 6, 37, 2, 9, 5, 21, 1, 6, 10, 2};
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        countSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void countSort(int[] arr) {
        //1.求出最大值和最小值
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        //2.开辟一个新数组（计数数组），大小为最大值-最小值-1
        int[] count = new int[max - min + 1];

        //3.写入数据到计数数组
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] - min;
            count[index]++;
        }
        //4.写出数据覆盖原来的数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index] = i + min;
                index++;
                count[i]--;
            }
        }


    }
}
